/**
 * @author LKQ
 * @date 2021/12/20 17:10
 * @description 分析，对于n位的数字串，奇数位有[n/2]个，[]为向下取整，偶数位有[(n+1)/2]个，
 * 由题意，是好数字则奇数位有‘2’，‘3’，’5’。‘7’，四种，偶数位有‘0’，‘2’，‘4’，‘6’，‘8’五种，那么总的可能性有
 * 5^[(n+1)/2] * 4^[n/2]，但是当n较大时，需要采用快速幂方法。
 * 第一种方式，迭代
 */
public class Solution {
    public static int  mod = 1000000007;
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countGoodNumbers(50));
    }

    public int countGoodNumbers(long n) {
        return (int) ((quickMul(5, (n+1)/ 2) * quickMul(4,  n /2)) % mod);
    }

    public long quickMul(long x, long N) {
       long res = 1L, mul = x;
       while (N > 0) {
           if (N % 2 == 1) {
               res = res * mul % mod;
           }
           mul  = mul * mul % mod;
           N /= 2;
       }
       return res;
    }
}
